package com.lwt.codetop.stack;

// 32. 最长有效括号

import java.util.Stack;

/**
 * 思路：背过
 */
public class LongestValidParentheses {
    public static void main(String[] args) {
        String s = ")()())";
        int res = longestValidParentheses(s);
        System.out.println(res);
    }

    private static int longestValidParentheses(String s) {
        int n = s.length();
        int res = 0;
        Stack<Integer> stk = new Stack<>();

        int start = -1; // 起点
        for (int i = 0; i < n; i++) {
            // 遇到左括号
            if(s.charAt(i) == '(') {
                stk.add(i);
            }else { // 遇到右括号
                if(stk.size() > 0){ // 非空则出栈，然后判断是带内匹配还是某段完整匹配，更新答案
                    stk.pop();
                    if(stk.size() > 0){ // 段内匹配（栈内还有元素）
                        res = Math.max(res, i - stk.peek());
                    }else { // 某段匹配（栈内元素为0）
                        res = Math.max(res, i - start);
                    }
                }else { // 遇到第一个右括号数量 > 左括号数量 的位置-->分段
                    start = i;
                }
            }
        }
        return res;
    }

}
